Few-shot Relational Reasoning via Connection Subgraph Pretraining
https://gyazo.com/62a514d5e634122d220faafc5beed34d
はじめに
NeurIPS22
Few-shotにおける knowledge graph completion task を行う
上図のように, Background KG (knowledge graph)とsupport setが与えられた状態で, Query setのrelationを推論するタスク
Connection Subgraph Reasoner (CSR)を提案
Few-shot KG Completion
KGは$ \mathcal{G} = (\mathcal{E}, \mathcal{R}, \mathcal{T}) で表される
ここで, $ \mathcal{E}, \mathcal{R}はそれぞれentityとrelationで, $ \mathcal{T}はtripletで$ \mathcal{T} = \{ (h, r, t) | h, t \in \mathcal{E}, r \in \mathcal{R} \}
Few-shotknowledge graph completion taskとは
$ r' \not \in \mathcal{R}なような$ r'について (=unseenなrelationについて)
support set$ S_{r'} = \{(h_k, r', t_k) | h_k \in \mathcal{E}\}_{k=1}^Kが与えられた状態で
$ Q_{r'} = \{(h_j, r', ?) | h_j \in \mathcal{E}\}_{j=1}^J の"?"に該当するentityを当てるタスク
https://gyazo.com/1f68ac20bf4a8b573c38243bf7f4da29
引用: M. Chen, W. Zhang, W. Zhang, Q. Chen, and H. Chen. Meta relational learning for few-shot link prediction in knowledge graphs. In EMNLP, 2019.
Inductive Reasoning
以下のようなものをhypothesisと呼ぶ
$ \exists Z, (h_c,\text{can be done with},{Z}) \land ({Z},\text{is located at},{t_c}) \implies ({h_c},{\bowtie},{t_c}).
基本的には有効なhypothesisを探すことを目的とする
General Framework
まずは一般化されたフレームワークを提案している
このフレームワークに則り, Learning-freeな方法(CSR-OPT)と学習可能な方法(CSR-GNN)の二つを提案している
1. Triplet Contextualization
support setとクエリのTripletに対して, background KGからサブグラフを作成する
具体的には, ノードからk-hopで到達しうるノードまでを使ってサブグラフを構成する
これにより知識グラフによって"contextualized"されたグラフを得ることができる
2. Hypothesis Proposal
一般にhypothesis proposal module と呼ばれる$ M_pを用いて, support setに対する全てのサブグラフに対してhypothesisを提案する
$ M_pはどのエッジを採用するかを示すsoft edge mask $ m: [0,1\rbrack^{E}を出力する
エッジを採用 = tripletを採用
$ \{m_i\}_{i= 1}^K = M_{p}(\{G(h_i, t_i) | (h_i, r', t_i) \in S_{r'}\})
$ b = \frac{1}{K} \sum_{i= 1}^K M_{enc}(G(h_i, t_i), m_i)
ただし, $ M_pは以下の式を満たす必要がある ($ sはcosine類似度)
$ \arg\max(\sum_{i= 1}^K \sum_{E} m_i), s.t. \:\: \forall i,j \in 1...K,\: s(M_{enc}(G(h_i, t_i) , m_i) ,\: M_{enc}(G(h_j, t_j) , m_j)) > 1- \epsilon
3. Hypothesis Testing.
一般にevidence proposal module $ M_eと呼ばれる $ M_eを用いてhypothesisが正しいかどうかを検証する
$ m_q = M_{e}(b, G(h_q, t_q))
$ score = s(b, M_{enc}(G(h_q, t_q), m_q))
ただし $ M_eは以下の式を満たす必要がある ($ sはcosine類似度)
$ s(M_{enc}(G(h_q, t_q) , m_q), b) > 1- \epsilon
CSR-OPT (Learning-free)
hypothesis proposal module$ M_pについて, 以下の最適化問題を解く
$ M_{p}(\{G(h_i, t_i) | (h_i, r', t_i) \in S_{r'}\}) = \arg\max \sum(\{m_i\}_{i= 1}^K) - \lambda * H(m_q)
$ s.t. \sum s(M_{enc}(G(h_i, t_i), m_i), M_{enc}(G(h_j, t_j), m_j)) > 1- \epsilon',
$ \texttt{connectivity}(m_i) > 1- \epsilon'
ただし, $ \texttt{connectivity}は$ Aを隣接行列, $ R_{i,j} = min((I + A + A^2)[i,j\rbrack, 1)として, 以下の通り
$ \texttt{connectivity}(m_i) =\frac{1}{|E|} \sum_{e = (n,n')\in E} m_{ie} * \min(R_{n,h_i} +R_{n,t_i}+R_{n',h_i}+R_{n',h_i}, 1)
おそらく $ k\texttt{-hop}, k \in [0,2\rbrackなので$ A^2とか出てくる
Aが無向または有向グラフGの隣接行列とすると、行列An(すなわちAのn個の複製の積)は興味深い解釈を持つ: 要素(i, j)は頂点iから頂点jへの長さnの(有向または無向)歩道の数を与える。nが、あるi、jについてAnの要素(i, j)が正となるような最小の非負整数とすると、nは頂点iと頂点jとの間の距離である。
evidence proposal module $ M_eについて, 以下の最適化問題を解く ($ H(\cdot)は正則化項)
$ T(b, G(h_q, t_q)) = \arg\max s(b, M_{enc}(G(h_q, t_q), m_q)) - \lambda * H(m_q)
$ M_{enc}はランダムなGNN (要検証)
CSR-GNN
$ f_{enc}(G_1, m_1): \mathcal{G} \times \mathbb{R}^{|\mathcal{E}|} \to \mathbb{R}^d, $ f_{dec}(G_2, b): \mathcal{G} \times \mathbb{R}^d \to \mathbb{R}^{|\mathcal{E}|}として, それぞれを$ M_p, $ M_eとする
$ f_{dec}にはPathConを使用
Relational Message Passing for Knowledge Graph Completion (KDD21)
https://gyazo.com/fda501ee93eb0c5df5c71e63f3b3c063
https://gyazo.com/15b9cc5fb1917994c11cff2df78d58bf
学習方法
reconstruction loss とcontrastive lossを使用
$ Loss_{recon} = \ell_{\text{CE}}(m, f_{dec}(G, f_{enc}(G, m)))
$ Loss_{contrast} = \max( s(g_{pos}, g) - s(g_{neg}, g) + \gamma, 0)
$ gに関して,
同じrelationに対して異なるtripetをサンプリングしてきたものを$ G, G'として正例と負例を作る
$ g = M_{enc}(G, m)
$ g_{pos} = M_{enc}(G, f_{dec}(G, f_{enc}(G, m)))
$ g_{neg} = M_{enc}(G',f_{dec}{G', f_{enc}(G, m)})
実際の推論例
https://gyazo.com/5371c5b74bdcca00c062ba0cc38655d5